package 比较排序;

public class HeapSort {

    public static void sort(int[] arr){
        //将数据整理成大顶堆
        for (int i=arr.length/2;i>=0;i--){
            buildMaxHeap(arr,i,arr.length);
        }
        for (int i=arr.length-1;i>0;i--){
            swap(arr,0,i);//把堆顶元素放到数组最后
            buildMaxHeap(arr,0,i);//重新整理成大顶堆
        }
    }

    private static void buildMaxHeap(int[] arr,int start,int length){
        int temp=arr[start];
        //从上到下，将较小的数下沉到堆底
        for(int i=2*start+1;i<length;i=2*i+1){
            if(i+1<length && arr[i]<arr[i+1]) i++;//判断左右孩子节点的大小
            if(temp>=arr[i]) break;//父节点大于它的左节点和右节点
            swap(arr,start,i);//父节点与大于父节点的孩子节点进行交换
            start=i;
        }
    }

    private static void swap(int[] arr,int i,int j){
        int temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
    }
}
